The use of complex numbers, and the arithmetic associated with such complex numbers affects many of us in our everyday lives. Complex numbers are two-dimensional numbers comprising a real component and an imaginary component, commonly represented mathematically in the form a+bi. Electromagnetic (EM) fields, such as those used in wireless communications (e.g., for our cellular phones, pagers, etc.), represent a prime example of how complex numbers touch our daily lives. An EM field, such as those passed to/from a cell phone in a wireless communication system, are well-suited to representation in complex form as an EM field is comprised of an electrical energy component (e.g., the “real” component of the complex value) and a magnetic energy field component (e.g., the “imaginary” component of the complex value).
The processing of EM fields, for example, relies heavily on the arithmetic of such complex numbers in general, and the multiplication and addition of such numbers in particular. Typically, such signal processing is performed in specially programmed general purpose processors often referred to as a digital signal processor. The advantage of using a DSP to perform the complex arithmetic is that (1) it is relatively easy to program to perform such tasks, and (2) the DSP is used to perform a number of other tasks and, therefore, obviates the need for additional devices. One significant problem with this approach is that the DSP is often burdened with a number of processing tasks and while relatively simple to implement in a DSP, complex arithmetic is very time consuming and represents a large drain on processor resources.
To illustrate the burden of complex arithmetic, equations (1) through (5), below provide a mathematical illustration of a process for multiplying two relative simple matrices.
                              (                                                    a                ⁢                                                                  ⁢                1                            +                              b                ⁢                                                                  ⁢                1                ⁢                j                                      ,                                          a                ⁢                                                                  ⁢                2                            +                              b                ⁢                                                                  ⁢                2                ⁢                j                                              )                ⁢                  (                                                                                          c                    ⁢                                                                                  ⁢                    1                                    +                                      d                    ⁢                                                                                  ⁢                    1                    ⁢                    j                                                                                                                                            c                    ⁢                                                                                  ⁢                    2                                    +                                      d                    ⁢                                                                                  ⁢                    2                    ⁢                    j                                                                                )                                    (        1        )                                =                                            (                                                a                  ⁢                                                                          ⁢                  1                                +                                  b                  ⁢                                                                          ⁢                  1                  ⁢                  j                                            )                        ⁢                          (                                                c                  ⁢                                                                          ⁢                  1                                +                                  d                  ⁢                                                                          ⁢                  1                  ⁢                  j                                            )                                +                                    (                                                a                  ⁢                                                                          ⁢                  2                                +                                  b                  ⁢                                                                          ⁢                  2                  ⁢                  j                                            )                        ⁢                          (                                                c                  ⁢                                                                          ⁢                  2                                +                                  d                  ⁢                                                                          ⁢                  2                  ⁢                  j                                            )                                                          (        2        )                                =                              (                                          a                ⁢                                                                  ⁢                1                ⁢                c                ⁢                                                                  ⁢                1                            -                              b                ⁢                                                                  ⁢                1                ⁢                d                ⁢                                                                  ⁢                1                                      )                    +                                    (                                                a                  ⁢                                                                          ⁢                  1                  ⁢                  d                  ⁢                                                                          ⁢                  1                                +                                  b                  ⁢                                                                          ⁢                  1                  ⁢                  c                  ⁢                                                                          ⁢                  1                                            )                        ⁢            j                    +                      (                                          a                ⁢                                                                  ⁢                2                ⁢                c                ⁢                                                                  ⁢                2                            -                              b                ⁢                                                                  ⁢                2                ⁢                d                ⁢                                                                  ⁢                2                                      )                    +                                    (                                                a                  ⁢                                                                          ⁢                  2                  ⁢                  d                  ⁢                                                                          ⁢                  2                                +                                  b                  ⁢                                                                          ⁢                  2                  ⁢                  c                  ⁢                                                                          ⁢                  2                                            )                        ⁢            j                                              (        3        )                                =                              (                                          a                ⁢                                                                  ⁢                1                ⁢                c                ⁢                                                                  ⁢                1                            -                              b                ⁢                                                                  ⁢                1                ⁢                d                ⁢                                                                  ⁢                1                                      )                    +                      (                                          a                ⁢                                                                  ⁢                2                ⁢                c                ⁢                                                                  ⁢                2                            -                              b                ⁢                                                                  ⁢                2                ⁢                d                ⁢                                                                  ⁢                2                                      )                    +                                    (                                                a                  ⁢                                                                          ⁢                  1                  ⁢                  d                  ⁢                                                                          ⁢                  1                                +                                  b                  ⁢                                                                          ⁢                  1                  ⁢                  c                  ⁢                                                                          ⁢                  1                                            )                        ⁢            j                    +                                    (                                                a                  ⁢                                                                          ⁢                  2                  ⁢                  d                  ⁢                                                                          ⁢                  2                                +                                  b                  ⁢                                                                          ⁢                  2                  ⁢                  c                  ⁢                                                                          ⁢                  2                                            )                        ⁢            j                                              (        4        )                                =                              (                                          a                ⁢                                                                  ⁢                1                ⁢                c                ⁢                                                                  ⁢                1                            -                              b                ⁢                                                                  ⁢                1                ⁢                d                ⁢                                                                  ⁢                1                            +                              a                ⁢                                                                  ⁢                2                ⁢                c                ⁢                                                                  ⁢                2                            -                              b                ⁢                                                                  ⁢                2                ⁢                d                ⁢                                                                  ⁢                2                                      )                    +                                    (                                                a                  ⁢                                                                          ⁢                  1                  ⁢                  d                  ⁢                                                                          ⁢                  1                                +                                  b                  ⁢                                                                          ⁢                  1                  ⁢                  c                  ⁢                                                                          ⁢                  1                                +                                  a                  ⁢                                                                          ⁢                  2                  ⁢                  c                  ⁢                                                                          ⁢                  2                                +                                  b                  ⁢                                                                          ⁢                  2                  ⁢                  c                  ⁢                                                                          ⁢                  2                                            )                        ⁢            j                                              (        5        )            This process can readily be extended to any length of complex vectors, and by extension, any size complex matrices.
At its core, the multiplication of complex numbers (complex multiply accumulate (CMAC)) begins with N×M binary digital multiplication, followed by the summing stages (wherein values are added/subtracted), and includes an additional accumulator stage. The combinatorial stage is often implemented with exclusive OR (XOR) gates that produce either N or M partial product terms (depending on the number of digits in the multiplicands). In the summing stage the partial products are added (e.g., within complex trees of carry-save adders) to produce a first interim product, which is passed to an accumulator. The accumulator adds the first interim product with accumulator bits resulting in the carry-save adders to output the final product. Thus, to perform this relatively simple multiplication at the atomic level of, for example, a digital signal processor (DSP) requires the following steps:
1. a1*c1, store product in accumulator;
2. b1*d1, subtract from accumulator;
3. a2*c2, add to accumulator;
4. b2*d2, subtract from accumulator, store in register as real component;
5. a1*d1, store in accumulator;
6. b1*d1, add to accumulator;
7. a2*d2, add to accumulator;
8. b2*c2, add to accumulator, store in register as imaginary component.
Thus, eight steps are required to complete the CMAC of these 2×2 matrices. Those skilled in the art will appreciate that when larger matrices are involved (e.g., signal processing within a wireless telephony application), the processing associated with the multiplication of complex numbers can quickly overwhelm even the most powerful DSPs.
In an effort to reduce the processing burden on the signal processor in performing complex number arithmetic, such as the multiplication example above, a number of alternate approaches ranging from simplifying the processing task, to offloading the processing of complex numbers to dedicated logic devices (e.g., programmable logic arrays (PLA), field programmable gate arrays (FPGA), and the like).
In this regard, more sophisticated multipliers have been developed that attempt to simplify the processing task associated with complex numbers through integration of a Wallace adder tree, and/or the Dadda bit-wise analysis of input terms. Each of the Wallace adder tree, and/or the Dadda bit-wise analysis technique are useful in simplifying the addition of binary terms which, as illustrated above, is germane to a multiplication process as well. To illustrate a conventional Wallace tree architecture, one branch of a conventional CMAC implementation is depicted in FIG. 1. Turning briefly to FIG. 1, the multiplier (100) receives a number of inputs (102) at the combinatorial stage (104), which generates a plurality of partial products (106A-N). These products are applied to a summing stage (108) incorporating a multi-stage, hierarchical tree of full-adders (110A-N) in accordance with a conventional Wallace tree architecture. The Wallace tree (110A-N) sums the input (e.g., partial product terms) according to bit significance (or magnitude). The Wallace tree output is passed to the accumulator stage (112) to generate the final product. The Dadda analysis may provide further optimization by specific analysis of bit-level operations.
While each of the Wallace and Dadda techniques provide improved performance over more conventional adder circuits, they rely heavily on a large number of full adder stages through which the signals must propagate. As a result, summing module designs (i.e., used as a stand-alone adder or in a multiplication application) employing a conventional Wallace-Dadda tree architecture are not well suited for implementation within, for example, a field programmable gate array (FPGA).
Thus, an architecture and related methods for performing efficient complex multiply-accumulates is presented, unencumbered by the deficiencies and limitations commonly associated with the prior art.